package demo13;

import demo11.Tree;

import java.util.ArrayList;
import java.util.List;

public class Tree3 {
        public static class TreeNode{
            public char val;
            public demo11.Tree.TreeNode left;
            public demo11.Tree.TreeNode right;
            public TreeNode (char val){
                this.val=val;
                this.left=null;
                this.right=null;
            }
        }
        //创建树
        public demo11.Tree.TreeNode creat()
        {
            demo11.Tree.TreeNode node1=new demo11.Tree.TreeNode('A');
            demo11.Tree.TreeNode node2=new demo11.Tree.TreeNode('B');
            demo11.Tree.TreeNode node3=new demo11.Tree.TreeNode('C');
            demo11.Tree.TreeNode node4=new demo11.Tree.TreeNode('D');
            demo11.Tree.TreeNode node5=new demo11.Tree.TreeNode('E');
            demo11.Tree.TreeNode node6=new demo11.Tree.TreeNode('F');
            demo11.Tree.TreeNode node7=new demo11.Tree.TreeNode('G');
            node1.left=node2;
            node1.right=node3;
            node2.left=node4;
            node2.right=node5;
            node3.left=node6;
            node3.right=node7;
            return node1;

        }
        //前序遍历
        public void prevnode(demo11.Tree.TreeNode head){
            if(head==null){
                return;
            }
            System.out.print(head.val+" ");
            prevnode(head.left);
            prevnode(head.right);
        }
        //中序遍历
        public void inorder(demo11.Tree.TreeNode head){
            if(head==null){
                return;
            }
            inorder(head.left);
            System.out.print(head.val+" ");
            inorder(head.right);
        }
        public  void pastorder(demo11.Tree.TreeNode head){
            if(head==null){
                return;
            }
            pastorder(head.left);
            pastorder(head.right);
            System.out.print(head.val+" ");
        }
        //第二种前序遍历
        List<Character> list=new ArrayList<>();
        public List<Character> pre(demo11.Tree.TreeNode head){
            if(head==null){
                return list;
            }
            list.add(head.val);
            pre(head.left);
            pre(head.right);
            return list;
        }
        //第三种前序遍历

        public List<Character> pre2(demo11.Tree.TreeNode head) {
            List<Character> list=new ArrayList<>();
            if(head==null){
                return list;
            }
            list.add(head.val);
            List<Character> list1=pre2(head.left);
            list.addAll(list1);
            List<Character> list3=pre2(head.right);
            list.addAll(list3);
            return list;
        }
        //二叉搜索树
  Tree. TreeNode prev=null;
    public void convertChild(Tree.TreeNode node){
            if(node==null){
                return;
            }
            convertChild(node.left);
            if(node.left==null){
            node.left=prev;
            }
            prev=node;
            convertChild(node.right);
    }
    public Tree.TreeNode convert(Tree.TreeNode node){
        if(node==null){
            return null;
        }
        convertChild(node);//修改指向
        Tree.TreeNode head=node;
        while (node.left!=null){
            node=node.left;
        }
        return node;
    }
}
